package com.LeeCode;

import java.util.HashMap;
import java.util.Map;

/**
 * 形成两个异或相等数组的三元组数目
 */

public class Code1442 {
    public static void main(String[] args) {
        int[] arr = {2, 3, 1, 6, 7};
        System.out.println(new Code1442().countTriplets(arr));
    }

    public int countTriplets(int[] arr) {
        int count = 0, n = arr.length;

        Map<Integer, Integer> cnt = new HashMap<>(), total = new HashMap<>();
        cnt.put(0, 1);
        total.put(0, 0); // 存放前缀和数组中的下标和
        int prefix = 0;
        for (int k = 0; k < n; k++) {
            prefix ^= arr[k];
            // 如果之前出现过相同的前缀异或值
            if (cnt.containsKey(prefix)) {
                // 累加结果：对于之前每个出现该值的位置i
                // 从i+1到k的每个j都满足条件，共(k-i)种选择
                count += cnt.get(prefix) * k - total.get(prefix);
            }
            // 更新统计信息
            cnt.merge(prefix, 1, Integer::sum);
            total.merge(prefix, k + 1, Integer::sum);
        }
        return count;
    }
}
